package leetcode.greed;

//在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
//
//        你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
//
//        如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/gas-station
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//gas  = [1,2,3,4,5]
//cost = [3,4,5,1,2]
//dd   = [-2,-2,-2,3,3]
//todo
public class Test134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] d = new int[cost.length];
        int total = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            d[i] = gas[i] - cost[i];
            total += d[i];
            if (d[i] > 0) {
                if (i > 0 && d[i - 1] < 0) {
                    start = i;
                }
            }

        }
        if (total < 0) {
            return -1;
        }
        int max = 0;
        int temp = 0;
        int result = -1;
        int left = start;
        while (true) {
            int index = left;
            while (d[index] > 0) {
                temp += d[index];
                if (temp >= max) {
                    result = left;
                }
                if (index == d.length - 1) {
                    index = 0;
                } else if (index == start - 1) {
                    return result;
                } else {
                    index++;
                }
            }
            while (d[left] < 0) {
                if (index == d.length - 1) {
                    index = 0;
                } else if (index == start - 1) {
                    return result;
                } else {
                    index++;
                }
            }

        }

    }
}
